class MinStack
{
public:
  stack<pair<int, int>> stk; // [原始数据, 栈最小值]

  MinStack()
  {
  }

  void push(int x)
  {
    if (stk.empty())
      stk.push(make_pair(
          x,
          x)); // 插入 pair(x,x)
    else
      stk.push(make_pair(
          x,
          min(x, stk.top().second))); // 插入 pair(x, 当前栈最小值)
  }

  void pop()
  {
    stk.pop();
  }

  int top()
  {
    return stk.top().first; // top.first 元素自己
  }

  int getMin()
  {
    return stk.top().second; // top.second 栈【最小】值
  }
};
